The Network Virtualization concept is used to provide separate logical networking environments (called Virtual Networks) over a single shared Networking Infrastructure (such as for example Network Provider backbone or Internet Service Providers). A Virtual Network (VN), known also as Overlay Network, is a group of Virtual Nodes achieved via node virtualization technology interconnected via Virtual Links (e.g. tunnels) achieved via data-path virtualization technology.
Virtual Network (VN) may be considered as a service provided “on demand” by a
Virtual Network Service Provider (VNSP) (such as carriers and network providers, Internet Service Providers) and delivered to Virtual Network Service (VNS) customers such as end-user clients (e.g. Personal Network user), enterprise customers (e.g. VPN customers) or Service Providers (such as VPN Service Providers, Routing Service Providers, QoS Service Providers, Internet service providers (ISPs), cellular operators, Application Service Providers (ASPs)...). A Virtual Network Service provides a logical networking environment responsible for supporting VNS customer control and data traffic, protocols and end-to-end services (such as QoS, VPN, Routing, etc). An SLA (service level agreement) is usually negotiated between VNS customers and their VNSPs offering Virtual Network services.
The VNSP may be either the owner of one or multiple network infrastructures (such as global Tier-1 ISP, network providers); or may be a third-party provider having an SLA with one or multiple network service providers and carriers offering network infrastructure capable of supporting their Virtual Networks Services deployment. A VNSP itself may be a VNS customer of another VNSP known as a “carrier of carriers” offering Virtual Network services. When the Virtual Network service is provided by a personal or private network, the VNSP is the user or equivalently the personal or private network itself. A person, an end-user, or a company may be viewed as a VNSP offering VNS to other persons or employees in the case of personal networks, group communications and federations of personal and private networks. The network domain administered by one single VNSP may be called a VNSP network.
A customer may want VNS from a VNSP network not administered by its VNSP but by other VNSPs. In this scenario, an inter-VNSP cooperation and negotiation (via an SLA) may be established to provide the desired VNS for customers visiting a network managed by different VNSPs.
By using the OSI model Layer 3 network virtualization technology, a Virtual Network comprises of a group of Virtual Routers (or Virtual Routing Instances) interconnected via Virtual Links (or tunnels). Hence, the Virtual Network Service (VNS) itself comprises two services: Virtual Routing Service (VRS) and Virtual Link Service (VLS). The VNSP provides a VNS comprising both VRS and VLS services.
The Virtual Link Service (VLS) may be achieved by either layer 2 or layer 3 tunnels (such as IPsec, MPLS, L2TP, GRE, IP-in-IP tunnels etc), or direct layer 2 of the OSI model connections such as ATM and Frame Relay. The Virtual Link Service (VLS) is offered to the VNS customer to interconnect the Virtual Routing Services (VRS) across the VNSP backbone.
The Virtual Routing Service (VRS) is a networking process which forwards VNS customer control and date traffic from sources to destinations, within the Virtual Network, based on routing tables and protocols. The Virtual Routing Service (VRS) is supported by VNSP edge routers located in the VNSP network. The VNSP edge routers may be any nodes located in the VNSP network that has routing capabilities. The VNSP edge routers may be provider edge routers, customer edge routers, wireless access routers, gateways, as well as any node in a personal or private network with routing capabilities.
The VNSP edge router may be based on the Virtual Routing concept (a node virtualization technology) to handle multiple Virtual Routing Services. The Virtual Routing concept subdivides a physical router into either multiple virtual routing and forwarding (VRF) instances or multiple independent and separate Virtual Routers (VRs) supported by the same physical router. Each VRF is composed of an IP routing table, a forwarding table, a set of interfaces that use the forwarding table and a set of protocols and rules responsible for associating Virtual Network routes to the appropriate forwarding table. Each Virtual Router (VR) may be an emulation of a physical router including mechanisms and tools for management, configuration, monitoring and maintenance. One virtual router instance may be seen as one VRF instance augmented by these additional mechanisms and tools. Each VR may have its own forwarding and routing tables and protocols, its own management and maintenance functions, its own IP network services, and its own physical or/and logical network interfaces. The VR may appear to the VNS customer as a dedicated physical router. Many VR instances may run on a single physical router by using Software based Virtualization approaches. VR instances may have independent IP routing and forwarding tables isolated from each other. VR instances may share centralised physical resources such as route processor and forwarding processor, memory to perform their routing and forwarding processing, but may be kept logically separated.
The VRS is supported by either one VRF or one VR instance in the VNSP physical edge router. A VRF instance may be viewed as a simplified VR instance composed only of a simple routing and forwarding instances. Accordingly, the term “VR instance” is to be read as encompassing a “VRF instance”.
An alternative technology, related to VRs implementation, called Logical Router (LR) or “Multi-router”, consists of handling, into one single chassis, multiple separated physical routers (Hardware based Virtualization) with dedicated processing and memory resources (compared to the VR technology using multiple Virtual Routers sharing physical resources). This technology provides a new model for control plane processing by providing distributed and dedicated route processing engines (e.g. CPUs) and memory buffers for each router. One logical router (LR) may support multiple Virtual Routers (VRs).
The virtual routing service (VRS) is used to support:                router consolidation, which means consolidating multiple logical/virtual routers into one single physical router, and which may be used to deploy edge, aggregation and core routers together in the same router chassis located in a network point of presence (PoP),        service and network consolidation thanks to which different IP services or different networking technologies, maintained by virtual routers, may be supported by the same physical router,        wholesale router business model which may be performed by selling to customers the access to and use of virtual routers hosted by providers,        per-Virtual Network routing services maintaining:                    IP connectivity and networking such as broadband access network connectivity, overlay networks,            value added IP network services such as IP virtual private network, IP quality of service (QoS), and voice over IP (VoIP), routing service,            service differentiation. For instance, per-application QoS guarantee may be provided by the virtual routing service technology since one virtual router can be dedicated for routing real-time applications, such as voice over IP (VoIP) and video conferencing, and another VR for routing best-effort applications and so on,            new network services deployment. Virtual routing service provides a virtual framework and network to support new routing and addressing spaces for new network services deployment (such as IPv6) in physical routers.                        
The idea of sharing underlying network infrastructures may provide to VNS customers (e.g. Service Providers, ISPs) the ability to extend their services, their reach and network coverage into new geographical areas and regions in a reliable, secure and scalable manner. VNSP like large backbone network providers and operators may offer cost-effective per-customer Virtual Network through their physical edge routers, located in their PoP, incorporating virtual routing technology. These physical edge routers may be shared by multiple service providers and ISPs (i.e. VNS customer) with no physical presence in the geographical area.
With this technology, ISPs (i.e. VNS customer) may not have to install new physical PoP and routers to offer IP services and connectivity such as for example wholesale broadband access services to end users located in new geographical regions and areas. They may simply allocate or purchase VNS service from a VNSP edge router of existing PoP already located in the area where the ISP intends to serve their end users with global Internet access. The customers may gain complete access to and management of their own virtual routers handled by the VNSP network.
An exemplary application of Virtual Network Services is related to network based IP virtual private network (VPN) services. VPN service providers use virtual routing technology to ensure private networking by offering per-VPN services to their customers (e.g. enterprise customers). A VPN service provider may be seen as a Virtual Network Service Provider (VNSP) offering secure Virtual Networks to VPN customers (i.e. VNS customers).
When a VNS customer requires virtual routing service(s) from its VNSP, an SLA may be established and operation and maintenance costs be negotiated. The VNSP may allocate, beforehand, virtual router instance(s) for the VNS customer during an initial VR provisioning phase and configure its physical routers to support the customer's VR(s).
The VNSP may assign to the customer's VR(s) the appropriate physical and logical network interfaces, ports, policies, routing functions and parameters based on customer-specific information and requirements and the SLA. In addition, the VNSP activates the appropriate routing protocol instances (customer and inter-VR routing protocols) related to the specific customer and backbone network requirements. Once the VR is successfully provisioned, the VNSP may either manage the customer VRs using management protocols, policies, and interfaces capable of activating and deleting the VR instances; or outsource the VRs management to the customers.
The first challenge may be the fact that a VNS customer may unpredictably require dynamic deployment of new IP service and reconfiguration of its provisioned VR, or may require new or temporary allocation and provisioning of new virtual router instances in certain physical edge routers which are either managed by its VNSP or managed by other VNSPs.
Indeed, customers may need a dynamic reconfiguration of their VRs due to routing information changes such as changing routing protocol, dynamic membership and topology update. Customers may also require dynamic deployment of new IP service (e.g. VPNs, NAT, firewall . . . ). Likewise, when customers visit new geographical areas or new VNSP networks, they may be dynamically bound to physical edge routers which do not maintain beforehand any VR configuration, for example when the physical edge router is managed by the customer's VNSP, or any SLA for example when the physical edge router is managed by other VNSP, for the new customers.
For instance, mobile VPN users may visit new geographical region and want temporary access to their remote private networks (remote VPN sites). The VNSP may then have to intervene to manually or remotely provision and configure, although not at run time, the on demand VPN routing service in its physical edge routers to support new VR instances or to ask other VPN Service Providers having common SLA to provision VRS services for their customers/users.
Another example concerns ISP customers which need to extend their networks reach and coverage to provide “temporary” global Internet access and connectivity to their end-user clients located in new geographical regions. “Temporary” means connectivity for a short period of time. The VNSP (global Tier1 ISP) may have to intervene to manually provision routing services for the ISP customers, in their appropriate edge routers.
In conclusion, the provisioning of new VR, deployment of new IP services, reconfiguration and removal of VRs installed in physical edge routers may require complete intervention of VNSP which manually provision VRS for their customers.
However, the frequent intervention of VNSPs each time a customer demands, unpredictably, dynamic reconfiguration and temporary allocation and provisioning of virtual routing service for just a short period of time may be neither efficient nor profitable for VNSPs and VNS customers. The manual VNSP involvement is costly, time-consuming process and can even increase provisioning and management complexity for service providers with possible service misconfigurations. The VNSP should provision and configure VRs for its customers quasi instantaneously and at run time without the need of any manual provisioning of on demand virtual routing services requested by customers. An automated VR service provisioning process may be required in this case.
Another challenge is that the VNS customer may need complete self-provisioning, self-control, self-configuration and self-management of their VRs without any VNSP intervention. In this case, the VNSP may authorise its customers to allocate and self-provision their VRs based on rules, policies, authorisation and access control procedures.
In fact, VNS customers may not trust any service provider to control their internal traffic and routing processing. VNS customers may also require personalising their routing protocols and VRs configuration through customisable self-service interfaces without the intervention of any service provider manipulation. The VNS customers may want to benefit from high performance forwarding supported by edge routers located in VNSP networks while remotely self-controlling their routing processing. This may improve networking scalability, flexibility and performance and may allow customers to have end-to-end routing control. However, current virtual routers designs allow only limited and restricted control and configuration operations authorised by the VRs administrator. Routing and forwarding processes are both configured and controlled by the VNSPs.
However, current virtual routers design does not provide a flexible and dynamic framework. A dynamic framework may enable configuration of installed VRs at run time, and be able to provision instantaneously new and on demand VRs for new customers. The current virtual routers design does not provide automated provisioning of on demand virtual routing services required by VNS customers.
A further limitation concerns the number of VR instances that a physical edge router can support e.g. scalability. Indeed, each VR instance uses physical router resources such as memory, processors . . . which are limited and depend on the router performance and capacity. Using different routing protocols in each VR instance such as the inter-VR routing, customer routing and backbone routing as well as using multiple tunnels per VR which depend on the VRs topology per VPN, may increase the resource utilisation and then decrease the number of VRs per physical edge router. A backbone VR may improve this scalability constraint by multiplexing tunnels in one tunnel established between backbone VRs pair.
Recently both the IETF ForCES (forwarding and control element separation) framework, proposed by the IETF (Internet Engineering Task Force) community and disclosed in the publication Yang, L., et al. “forwarding and control element separation (ForCES) framework”. RFC 3746, April 2004, and the SoftRouter router disclosed by US 2006 0092940 are providing disaggregation concept of router hardware from router software using standard interfaces and protocols. ForCES and SoftRouter disclose architectures that separate the control plane from the forwarding plane functions. Two logical entities have been defined:                control element (CE) responsible for performing routing, signalling and control functionality in the router,        forwarding element (FE) responsible for performing forwarding and switching functionality in the router.        
Two protocols are used to manage and communicate with the CEs and FEs entities: dynamic binding protocol and FE/CE transport protocol.
The dynamic binding protocol is responsible for discovering CEs and FEs availability and capabilities, and the association between them. Once the binding is established, the FE/CE transport protocol communicates and exchanges data and control information between the separated CEs and FEs. The ForCES working group is currently defining the ForCES protocol specifications [A. Doria, et al., “ForCES protocol specification”, Internet draft, March 2006] to standardise information exchange between the control and the forwarding plane in a ForCES router.
Two association phases are considered: pre-association phase and post-association phase:
During the pre-association phase, a CE manager and FE manager determine which CEs and FEs are composing the router:
The CE manager is a logical entity that maintains the list of CEs performing the router control plane and is responsible for the FE discovery process by determining with which FE(s) a CE should communicate within the ForCES router.
The FE manager is a logical entity that maintains the list of FEs performing the router forwarding plane and is responsible for the CE discovery process by determining to with which CE(s) an FE should communicate within the ForCES router.
The SoftRouter dynamic binding protocol may operate in the pre-association phase between the CE manager and FE manager to exchange and communicate CE/FE discovery process information. The CE manager (respectively the FE manager) informs the CEs (respectively informs the FE(s)) of the CEs-FEs association decisions made during the pre-association phase.
In the post-association phase, and once the FE(s) and CE(s) know each other, communication between CEs and FEs inside the router, including exchange of data packets and control messages is achieved via the FE/CE transport protocol (such as the ForCES protocol).
FIG. 1 represents the functional model of a network node system, called also Virtual Routers system, for providing VRs as well as its implementation in a physical edge router 309.
As depicted in FIG. 1, the physical edge router 309, such as a provider edge (PE) router, that implements the virtual routers system may be connected to two networks: customer networks 305 and backbone networks 306. Physical network connections 321, such as for example Ethernet cable, optical fibre, radio links, may connect the edge router 309 to both customers and backbone networks. Multiple VR instances may be running on the physical edge router.
FIG. 1 details a virtual router instance 300 design comprising three interdependent functional planes: management plane 301, control plane 302 and forwarding plane 303. Other VR instances 322 handled by the physical edge router 309 may have the same functional model design as VR 300.
The management plane of the physical edge router may be subdivided into multiple logical VR management domains.
The VNSP may be able to manage separately VRs installed in its edge router. Each VR management plane may include maintenance, monitoring and management functions.
FIG. 1 depicts an example of a management plane 301 of VR 300. Management information data base module such as policy information base (PIB) and management information base (MIB) module objects may be used and managed through management protocols such as common open policy service (COPS) and simple network management (SNMP) protocols. Each VR instance may have a unique identifier (VR-ID) used by the VNSP to bind physical and logical network interfaces to the VR and to configure its parameters and networking processes. The VNSP may also use the VR identifier (VR-ID) to create, activate and delete the VR instance.
FIG. 1 depicts an example of control plane 302 of VR 300. The control plane 302 includes routing processes, signalling, value added IP services (VPN tunnelling, QoS, NAT, security (firewall), etc. . . . ). Just like a physical router, routing protocols and table, QoS functions (metering, shaping, classification, policing and scheduling), security functions (policy based routing, firewall, access list), tunnelling mechanisms (e.g. IPsec key negotiation) and signalling protocol (e.g. RSVP) may be configurable and controllable on a per-virtual routing service basis within a VR.
The routing processes 317 of control plane 302 may implement routing protocols responsible for creating routing tables (routing information bases, or RIBs) based on the network topology and routing information exchanged with neighbouring routers. Each VR instance may maintain three independent routing processes:                inter-VR routing process 319 used to distribute routing information, such as VPN reachability information, via tunnels or directed network links between the VR 300 and other neighbouring VRs that are members of the same virtual routing service,        customer routing process 318 used between the VR 300 and the customer routers (e.g. customer edge routers in the case of VPN routing service); the routing protocol used in the VR is the same as the one used in the customer network (e.g. VPN site) attached to the VR,        backbone routing process used between the VR 300 and the VNSP backbone network. This routing process may be needed for exchanging connectivity information (e.g. tunnel information) between VRs using the backbone routing protocol. The VRs may use a backbone VR 312, for the backbone routing process across the backbone. In this case, the VR 300 may not need to handle a specific backbone routing process.        
FIG. 1 also depicts the forwarding plane 303 (or data plane) of VR 300: this plane handles the VR forwarding process 320 responsible for packet processing and forwarding functions in the VR and supports a forwarding table, for example a forwarding information base 330 (FIB), updated by the routing processes and used to forward IP packets. Packets are forwarded to customer and neighbouring routers via virtual network connections 307 for example such as IPsec tunnels, established over physical network connections 321, such as for example Ethernet cable, optical fibre, wireless connections.
A particular VR instance, called basic virtual router instance 304, represents the main router of the physical edge router and is reserved for the VNSP administrator that manages the VRs. The same VR planes and functionalities previously described may be used in the basic virtual router instance 304. This particular VR instance 304 may include auto-discovery mechanisms needed by the other VR instances to automatically distribute and exchange control VPN information. The basic virtual router instance may support the backbone routing process and may also maintain the optional backbone VR 312 that performs the backbone routing process in this case.
A physical edge router 309, such as PE, may support multiple VR instances that share its physical resources such as physical control engines 313 including for example memory and route processors, physical forwarding engines 314 including for example memory and forwarding processors and network interfaces 316, such as for example line cards, network interface cards.
The route processor which is for example a general-purpose processor included in the physical control engine 313 performs routing processes of VRs (such as routing processes 317). The route processor may use memory modules to store routing information and tables.
The physical forwarding engine 314 may include hardware engines responsible for performing forwarding processes of VRs, such as forwarding process 320, and they may either be centralised or distributed in line cards, daughter boards or stand-alone boxes. The physical forwarding engine may include memory and forwarding processors which may comprise network processors, ASIC (Application Specific Integrated Circuit), programmable network processing units (NPUs) or general-purpose processors. The physical forwarding engines 314 may communicate with physical control engines 313 through switch fabrics 315.
The network interfaces 316 may support multiple physical network connections 321 such as for example Ethernet cable, optical fibre, wireless connections to satisfy customer and backbone networks connectivity. The network interfaces may be either logical or physical interfaces directly connected with the physical forwarding engines 314. In the case of using line cards as physical network interfaces, the physical forwarding engines 314 may be distributed in the line cards. Each VR may have dedicated logical or/and physical interfaces. Multiple VRs may share physical network interfaces by using multiple logical network interfaces.